#include <iostream>
#include <stdio.h>
using namespace std;

//斐波那契数列-递归
int recursion(int n){
	if (n==1)
	    return 1;
	if (n==2)
	    return 1;
	int b = recursion(n-1)+recursion(n-2);
	return b; 
}

//斐波那契数列-递推
int recurrence(int n){
        if(n <= 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        int a=1, b=2, c=0;
        for(int i=3; i < n; i++){ //空间复杂度 O(n)
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

int main(){
	cout << "请输入n: ";
	int i = 0;
	cin >> i; 
//	printf("%d",recursion(i)); 
    printf("%d",recurrence(i)); 
	return 0;
}